# 给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
#  叶子节点 是指没有子节点的节点。
#
#  示例 1：
# 输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
# 输出：[[5,4,11,2],[5,8,4,5]]
#
#  示例 2：
# 输入：root = [1,2,3], targetSum = 5
# 输出：[]
#
#  示例 3：
# 输入：root = [1,2], targetSum = 0
# 输出：[]
from com.example.tree.tree_node import TreeNode
from typing import Optional, List


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        pathList = []
        def dfs(root: Optional[TreeNode], targetSum: int) -> None:
            """
            dfs + 回溯
            :param root:
            :param targetSum:
            :return:
            """
            if not root:
                return
            pathList.append(root.val)
            if targetSum == root.val and not root.left and not root.right:
                res.append(list(pathList))
            dfs(root.left, targetSum - root.val)
            dfs(root.right, targetSum - root.val)
            pathList.pop()  # 当前路径不满足条件，需要回溯状态
        dfs(root, targetSum)
        return res


if __name__ == "__main__":
    # root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
    #                  5
    #         4                     8
    #     11                  13          4
    #  7      2                       5       1
    root = TreeNode(5)
    root.left, root.right = TreeNode(4), TreeNode(8)
    root.left.left, root.right.left, root.right.right = TreeNode(11), TreeNode(13), TreeNode(4)
    root.left.left.left, root.left.left.right, root.right.right.left, root.right.right.right = TreeNode(7), TreeNode(2), TreeNode(5), TreeNode(1)
    targetSum = 22
    print(Solution().pathSum(root, targetSum))
